package com.test.daily.leetcode.y2022.m05.day0526.v05;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/26 下午 11:24
 * @version: 1.0
 */
public class Solution {
    public static class UnionFind{
        public int[] parent;
        public int[] size;
        public int sets;
        public int[] help;
        public UnionFind(int[] arr){
            int  N = arr.length;
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                size[i] = 1;
            }
            sets = N;
        }
        public int findFather(int i){
            int hi = 0;
            while(i != parent[i]){
                help[hi++] = i;
                i = parent[i];
            }
            for(hi--; hi >=0; hi--){
                parent[help[hi--]] = i;
            }
            return i;
        }
        public void union(int i, int j){
            int iHead = findFather(i);
            int jHead = findFather(j);
            if(iHead != jHead){
                if(size[iHead] > size[jHead]){
                    size[iHead] += size[jHead];
                    parent[jHead] = iHead;
                } else {
                    size[jHead] += size[iHead];
                    parent[jHead] = iHead;
                }
                sets--;
            }
        }
        public int sets(){
            return this.sets;
        }
    }
}
